
/**
*程序7.1 快速排序  
*如果r等于或小于1，则说明数组只有一个元素或者没有元素。
* 否则，这数组会被partition函数处理，partition函数是将a[i]放入位置，而i大于或等于l且小于或等于r，然后重新整理元素顺序，通过合适的递归完成排序。 
*/
#include <stdio.h>
#include <stdlib.h>

//考虑移植性的问题，才把类型都定义为Item，这就可以随时改为浮点float都可以
typedef int Item;

#define key(A) (A)
//使用宏的一个好处，不用考虑参数的类型
#define less(A, B) (key(A) < key(B))
#define exch(A, B)  \
    {               \
	Item t = A; \
	A = B;      \
	B = t;      \
    }
#define compexch(A, B) \
    if(less(B, A))     \
    exch(A, B)
/**
  * 程序7.2 Partiioning 
  * v变量保存分割元素a[r]，而i和j分别是左右的扫描指针。
  * 这个partitioning循环是增长i和减少j，同时维护这不变的属性“没有左边的有元素大于v和没有右边的元素小于v”。
  * 一旦两个指针相遇，我们就交换a[i]和a[r]完成partitioning，也就是将v放入a[i]值里。
  * partitioning循环被写成一个无限循环，当两个指针交叉后则中断循环。判断j==l是预防这种情况“分割元素是最小的元素”。
  * 
 */
int partition(Item a[], int l, int r){
	int i = l-1,j=r; Item v = a[r];
	for(;;){
		while(less(a[++i],v));
		while(less(v,a[--j])) if(j==l) break;
		if(i>=j) break; //cross
		exch(a[i],a[j]);
	}
	exch(a[i],a[r]);
	return i;
}
void quicksort(Item a[], int l, int r)
{
     int i;
	 if(r<=l) return;
	 i = partition(a,l,r);
	 quicksort(a,l,i-1);
	 quicksort(a,i+1,r);
}

main(int argc, char* argv[])
{
    int i, N = atoi(argv[1]), sw = atoi(argv[2]),j=0;
    int* a = malloc(N * sizeof(int));
	printf("%d items\n",N);
    if(sw)
	for(i = 0; i < N; i++) {
	    a[i] = 1000 * (1.0 * rand() / RAND_MAX);
		printf("%d item is %d\n",i,a[i]);
	}
    else
/** 不知道是不是我的知识不够，书本上的例子这段代码运行不起来
	while(scanf("%d", &a[N]) == 1)
	    N++; 
		 */
	while(j<N){
		scanf("%d",&a[j++]);
	}
	//2.调用里快速排序的函数对这些整型进行排序
	printf("call quicksort method\n");
    quicksort(a, 0, N - 1);
	//3.输出排序后的结果
    for(i = 0; i < N; i++)
		printf("%5d", a[i]);
    printf("\n");
}
